A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs

摘要

This work deals with a class of problems under interval data uncertainty,namely interval robust-hard problems, composed of interval data min-max regretgeneralizations of classical NP-hard combinatorial problems modeled as 0-1integer linear programming problems. These problems are more challenging thanother interval data min-max regret problems, as solely computing the cost ofany feasible solution requires solving an instance of an NP-hard problem. Thestate-of-the-art exact algorithms in the literature are based on the generationof a possibly exponential number of cuts. As each cut separation involves theresolution of an NP-hard classical optimization problem, the size of theinstances that can be solved efficiently is relatively small. To smooth thisissue, we present a modeling technique for interval robust-hard problems in thecontext of a heuristic framework. The heuristic obtains feasible solutions byexploring dual information of a linearly relaxed model associated with theclassical optimization problem counterpart. Computational experiments forinterval data min-max regret versions of the restricted shortest path problemand the set covering problem show that our heuristic is able to find optimal ornear-optimal solutions and also improves the primal bounds obtained by astate-of-the-art exact algorithm and a 2-approximation procedure for intervaldata min-max regret problems.